Міністерство науки і освіти України. Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій. Кафедра ПЗ Звіт До лабораторної роботи №5 За курсом «Алгоритми і структури даних». Тема роботи: Ознайомлення із методами сортування. Зокрема із методом швидкого сортування. Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із швидким методом сортування. Виконати лабораторну роботу використавши здобуті знання по методам сортування, зокрема по швидкому методу. ТЕОРЕТИЧНІ ВІДОМОСТІ "Швидке сортування", хоч і було розроблено більше 40 років тому, є найбільше вживаним і одним з найефективніших алгоритмів сортування. Метод заснований на підході "разділяй і керуй". Загальна схема така: з масиву вибирається деякий контрольний елемент а, запускається процедура розділення масиву, яка переміщає всі ключі, менші, або рівні а, ліворуч від нього, а всі ключі, більші, або рівні а[i] – в право тепер масив складається з двох підмножин, причому ліве менше, або рівно правого для обох підмасивів: якщо в підмасиві більше двох елементів, рекурсивно запускаємо для нього ту ж процедуру. В кінці вийде повністю відсортована послідовність. Розділення масиву На вході масив а[0]...a[N] і контрольного елементу p, по якому проводитиметься розділення. Введемо два індекса: i і j. На початку алгоритму вони вказують, відповідно, на лівий і правий кінець послідовності. Переміщати покажчик i з кроком в 1 елемент у напрямку до кінця масиву, поки не буде знайдений елемент а[i] >= р. Потім аналогічним чином почнемо переміщати покажчик j від кінця масиву до початку, поки не буде знайдений а[j] <= р. Якщо i <= j, міняємо а[i] і а[j] місцями і продовжуємо переміщати i та j по тих же правилах. Повторюємо крок 3, поки i <= j. Завдання: Впорядкувати одновимірний масив методом Шела. Повторити декілька раз з різною кількістю елементів та порівняти час виконання. Код програми #include<stdio.h> #include<stdlib.h> #include<time.h> #include<conio.h> int partition (int m[], int a, int b) { int i=a,j,t; for ( j=a; j<=b; j++) { if (m[j] <= m[b]) { t = m[i]; m[i] = m[j]; m[j] = t; i++; } } return i-1; } void quicksort (int m[], int a, int b) { int c; if (a >= b) return; c = partition (m, a, b); quicksort (m, a, c-1); quicksort (m, c+1, b); } int verify(int N[], int d) { int k; for (k=0;k<d-1;k++) if (N[k]>N[k+1]) return 0; return 1; } void main(void) { int N[100000],M[100000]; int i,j,m; int C[5]={10000,20000,50000,80000,100000}; clock_t start, end; clrscr(); for (i=0;i<5;i++) { for (j=0;j<C[i];j++) N[j]=rand(); start=clock(); quicksort (N, C[i],0); end=clock(); break; printf ("%d - %.3f - %s\n", C[i], (end-start)/CLK_TCK, verify(N, C[i]) ? "OK" : "Error"); } getch(); } Протокол роботи програми:
Висновок: Час роботи алгоритму сортування залежить від збалансованості, що характеризує розбиття. Збалансованість, у свою чергу залежить від того, який елемент обрано як опорний (відносно якого елемента виконується розбиття). Якщо розбиття збалансоване, то асимптотично алгоритм працює так само швидко як і алгоритм сортування злиттям. У найгіршому випадку, асимптотична поведінка алгоритму настільки ж погана, як і в алгоритму сортування включенням.